{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 align=\"center\"> Anagrams using Python </h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is an Anagram?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Task: Write a program that takes in a word list and outputs a list of all the words that are anagrams of another word in the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While there are many different ways to solve this problem, this notebook gives a couple different approaches to solve this problem. \n",
    "For each of the approaches below, we first define a word list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "word_list = ['percussion',\n",
    "             'supersonic',\n",
    "             'car',\n",
    "             'tree',\n",
    "             'boy',\n",
    "             'girl',\n",
    "             'arc']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 1: For Loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "temp = word_list[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['c', 'e', 'i', 'n', 'o', 'p', 'r', 's', 's', 'u']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['percussion', 'supersonic', 'car', 'tree', 'boy', 'girl', 'arc']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# initialize a list\n",
    "anagram_list = []\n",
    "\n",
    "for word_1 in word_list: \n",
    "    for word_2 in word_list: \n",
    "        if word_1 != word_2 and (sorted(word_1)==sorted(word_2)):\n",
    "            anagram_list.append(word_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['percussion', 'supersonic', 'car', 'arc']\n"
     ]
    }
   ],
   "source": [
    "print(anagram_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['c', 'e', 'i', 'n', 'o', 'p', 'r', 's', 's', 'u']\n"
     ]
    }
   ],
   "source": [
    "print(sorted('percussion'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['c', 'e', 'i', 'n', 'o', 'p', 'r', 's', 's', 'u']\n"
     ]
    }
   ],
   "source": [
    "print(sorted('supersonic'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 2: Dictionaries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sorting of lists in Python is O(nlogn) versus O(n) with a dictionary. If you have difficulty understanding the dictionary get method, I encourage you to see one of the following tutorials: [Python Dictionary and Dictionary Methods](https://hackernoon.com/python-basics-10-dictionaries-and-dictionary-methods-4e9efa70f5b9) or [Python Word Count](https://codeburst.io/python-basics-11-word-count-filter-out-punctuation-dictionary-manipulation-and-sorting-lists-3f6c55420855). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def freq(word):\n",
    "    freq_dict = {}\n",
    "    for char in word:\n",
    "        freq_dict[char] = freq_dict.get(char, 0) + 1\n",
    "    return freq_dict "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['percussion', 'supersonic', 'car', 'arc']\n"
     ]
    }
   ],
   "source": [
    "# initialize a list\n",
    "anagram_list = []\n",
    "for word_1 in word_list: \n",
    "    for word_2 in word_list: \n",
    "        if word_1 != word_2 and (freq(word_1) == freq(word_2)):\n",
    "            anagram_list.append(word_1)\n",
    "print(anagram_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'p': 1, 'e': 1, 'r': 1, 'c': 1, 'u': 1, 's': 2, 'i': 1, 'o': 1, 'n': 1}\n"
     ]
    }
   ],
   "source": [
    "print(freq('percussion'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'s': 2, 'u': 1, 'p': 1, 'e': 1, 'r': 1, 'o': 1, 'n': 1, 'i': 1, 'c': 1}\n"
     ]
    }
   ],
   "source": [
    "print(freq('supersonic'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('c', 1),\n",
       " ('e', 1),\n",
       " ('i', 1),\n",
       " ('n', 1),\n",
       " ('o', 1),\n",
       " ('p', 1),\n",
       " ('r', 1),\n",
       " ('s', 2),\n",
       " ('u', 1)]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(list(freq('percussion').items()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('c', 1),\n",
       " ('e', 1),\n",
       " ('i', 1),\n",
       " ('n', 1),\n",
       " ('o', 1),\n",
       " ('p', 1),\n",
       " ('r', 1),\n",
       " ('s', 2),\n",
       " ('u', 1)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(list(freq('supersonic').items()))"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
